/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package item26;

import org.junit.Assert;
import org.junit.Test;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:HasSubtree.java v1.0 2018/8/4 下午11:46 LvJing Exp $
 */
public class HasSubtree {

    /**
     * 面试题26：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
     * 思路：要判断tree2是否能为tree1的一颗子树，可以遍历tree1，当找到一个value跟tree2.root.value一样的节点时，判断以这个tree1的节点
     * 是否能跟tree2对上，对不上又去遍历其他的tree1节点，总之value一样时就是突破口，找到value一样的节点就可以进行判断结构是否跟tree2一样。
     */
    public class Solution {
        public boolean HasSubtree(TreeNode root1, TreeNode root2) {
            boolean hasFlag = false;
            if (root1 == null || root2 == null) {
                return false;
            }
            // 当遇到遍历tree1的节点值等于tree2的根节点值时，进行两者树的值比较
            if (root1.val == root2.val) {
                hasFlag = doesEqualsTree(root1, root2);
            }
            // 依然不匹配，对当前tree1节点的左节点进行匹配
            if (!hasFlag) {
                hasFlag = HasSubtree(root1.left, root2);
            }
            // 依然不匹配，对当前tree1节点的右节点进行匹配
            if (!hasFlag) {
                hasFlag = HasSubtree(root1.right, root2);
            }
            return hasFlag;
        }

        private boolean doesEqualsTree(TreeNode root1, TreeNode root2) {
            // 对比时tree2已经为空，证明tree2对比完毕，前面都通过了就肯定相等
            if (root2 == null) {
                return true;
            }
            // 对比时发现tree1就没有了，证明跟tree2肯定对不上，tree2都还没完
            if (root1 == null) {
                return false;
            }
            // 比较时发现值都不等了，肯定不匹配
            if (root1.val != root2.val) {
                return false;
            }
            // 再递归遍历左子树和右子树
            return doesEqualsTree(root1.left, root2.left) && doesEqualsTree(root1.right, root2.right);
        }
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    @Test
    public void test01() {
        Solution solution = new Solution();
        TreeNode tree1 = new TreeNode(1,
                new TreeNode(2, new TreeNode(6, new TreeNode(3), new TreeNode(5)), new TreeNode(7)),
                new TreeNode(6, new TreeNode(9), new TreeNode(4)));
        TreeNode tree2 = new TreeNode(6, new TreeNode(9), new TreeNode(4));
        Assert.assertTrue(solution.HasSubtree(tree1, tree2));
    }
}
